Cite this Article
Jin Lei, Wang Xiaojuan, Zhang Yong, You Jingwen. Cascading failure in multilayer networks with dynamic dependency groups*

Project supported by the National Natural Science Foundation of China (Grant No. 61601053).

. Chinese Physics B, 2018, 27(9): 098901  
Permissions
Cascading failure in multilayer networks with dynamic dependency groups*

Project supported by the National Natural Science Foundation of China (Grant No. 61601053).

Jin Lei, Wang Xiaojuan †, Zhang Yong, You Jingwen
Beijing University of Posts and Telecommunications, Beijing 100876, China

 

† Corresponding author. E-mail: wj2718@163.com

Project supported by the National Natural Science Foundation of China (Grant No. 61601053).

Abstract

The cascading failure often occurs in real networks. It is significant to analyze the cascading failure in the complex network research. The dependency relation can change over time. Therefore, in this study, we investigate the cascading failure in multilayer networks with dynamic dependency groups. We construct a model considering the recovery mechanism. In our model, two effects between layers are defined. Under Effect 1, the dependent nodes in other layers will be disabled as long as one node does not belong to the largest connected component in one layer. Under Effect 2, the dependent nodes in other layers will recover when one node belongs to the largest connected component. The theoretical solution of the largest component is deduced and the simulation results verify our theoretical solution. In the simulation, we analyze the influence factors of the network robustness, including the fraction of dependent nodes and the group size, in our model. It shows that increasing the fraction of dependent nodes and the group size will enhance the network robustness under Effect 1. On the contrary, these will reduce the network robustness under Effect 2. Meanwhile, we find that the tightness of the network connection will affect the robustness of networks. Furthermore, setting the average degree of network as 8 is enough to keep the network robust.

PACS: 89.75.Fb;05.10.-a
Keyword:cascading failure;dependency group;multilayer network
1. Introduction

The complex network has a wide range of applications in nature,[1,2] society,[3–5] computers,[6,7] and so on. The network property can be analyzed from different angles, such as network behavior, robustness, and controllability. Cascading failure[8,9] is a phenomenon which exists widely in the networks. Besides, analyzing cascading failure can support the construction of robust networks. In reality, networks often depend on each other. Multilayer network models are constructed to analyze the interdependent relation between networks. In this study, we mainly focus on cascading failure in multilayer networks.

Cascading failure means that some nodes’ failure in the network leads to other nodes’ failure because of the cascading effect. Early research regarded the cascading process as a process of load redistribution.[10] Removing several nodes and redistributing the loads of the removed nodes to adjacent nodes may cause further failure. Tian et al.[11] investigated the cascading failure in interdependent scale-free networks considering the coupling preference. They found that assortative connections in the community is beneficial to the network robustness. Li et al.[12] analyzed the cascading failure process in the networks with asymmetric dependence. The result showed that the asymmetric dependence made networks more robust than the symmetric one. Mizutaka et al.[13] studied the cascading failure caused by fluctuating loads in scale-free networks. Lehmann et al.[14] built a stochastic load-redistribution model for the cascading failure, which was thought to be more close to reality. Witthaut et al.[15] studied the percolation of cascading failures with a focus on the nonlocal effect occurring far away from the initial failure. They also found countermeasures based on the intentional removal of additional edges. Zhang et al.[16] found that interdependency could lead to an improved robustness for each individual network in a flow redistribution model. Mirzasoleiman et al.[17] considered three node weight strategies in the cascading failure model. He did simulations in real world networks such as power grid, the internet in the autonomous system, and the railway network of Europe. Wang et al.[18] studied the influence of coupled strength in interdependent networks, and found that when the coupled strength between two networks was weak, attacking the edges with low loads was more likely to trigger the cascading failure. Wang et al.[19] adopted three link patterns between interdependent networks and changing link patterns could improve the robustness of networks. So many studies have concentrated on the cascading model based on load redistribution. Recently, dependency property has been proposed to analyze the evolution of the complex network.

In dependency models, nodes are dependent upon each other. If there is more than a certain percentage of failed nodes in a dependency group, all the nodes in the group will fail. Parshani et al.[20] presented a framework to analyze the robustness of the network that included both connection and dependency links. The research showed that high density of dependency links made networks disintegrate faster during the cascading failure. Wang et al.[21] proposed a percolation model considering dependency links and found that this type of percolation with dependency group was always the first order. Kornbluth et al.[22] studied dependent links between networks which were based on distance, and found that networks with long dependency distances were much more vulnerable than networks with short dependency distances. Parshani et al.[23] found that changing the coupling strength of the interdependent networks could increase the robustness of the networks. However, static dependency links are not appropriate for real complex situation. For example, in financial networks, the cooperation between companies may change.

It seems more proper to introduce the dynamic dependency group to the network evolution. In the real situation, the dependency groups is common. For example, in financial networks, the trading and sale connections between companies can be viewed as links of networks. The companies in the same industrial chain may form a dependency group. When the amount of failed companies in the group exceeds a certain value, all other companies also fail due to symbiosis. At the same time, the companies in the same industrial chain will help each other because of the cooperation in chains. Another example is social network. The information and rumors can spread in the network. In social networks, each person reacts adaptively to their own changing situations and interests, which leads to dynamical dependency groups. There are several studies about dynamic dependency links in networks. McCulloh et al.[24] thought that people in the social network reacted adaptively to their own changing propensities and capabilities, leading to dynamic dependency. Bai et al.[25] analyzed the cascading failure with the dynamic dependency group and the percolation process, and put forward that the proportion and size of dependency groups could affect the network robustness. Besides, the recovery mechanism during the cascading failure of networks should be considered. Gong et al.[26] presented a recovery robustness index to evaluate the resilience of coupled networks to the cascading failure. Hu et al.[27] investigated recovery strategies to the cascading process in infrastructure networks. Their strategic repair methods showed similar effectiveness as the greedy repair. Majdandzic et al.[28] researched on the effect of local node recoveries and stochastic contiguous spreading. However, there are few studies on cascading failure with dynamic dependency groups in multilayer networks.

In this study, a model concentrating on the cascading failure in multilayer networks is built. We also take the dynamic dependency groups and recovery mechanism into consideration. Cascading failure in multilayer network can be divided into the process within layers and the process between layers. During the process within layers, cascading failure in dependency groups and percolation occur. During the process between layers, interdependent nodes affect each other. We define two effects between layers in this study. One effect reduces the network robustness, while the other improves the network robustness. The theoretical analysis which deduces the giant connected component in our model is given, which is verified by the simulation result. In the simulation, we study the influence factors of the network robustness in our model. The fraction of dependent nodes and the size of the dependency group are related to the network robustness. Besides, increasing the network connection tightness can enhance the network robustness.

The rest of the paper is arranged as follows. Section 2 puts forward the multilayer cascading model and describes the dependency relation in our model. We give a theoretical analysis of our model and verify our derivation with simulation in Section 3. Section 4 presents a simulation analysis of our model. Section 5 gives a conclusion of our work.

2. Multilayer networks cascading model

In this study, we mainly focus on the cascading failure in multilayer networks. A multilayer model with dynamic dependency groups, under the existence of the cascading effect and a recovery mechanism, is introduced. In multilayer networks, there are reactions within layers and reactions between layers. We can use M = (N, E) to represent a multilayer network, where N = {Nα; α ∈ {1,2, …}} is the set of single layer networks. Besides,

is the set of edges between layers. Here we set the connection between layers to be one-to-one. In a single-layer network, a fraction q of nodes are initially chosen to form the dependency groups with size g. All other (1 − q) nodes do not belong to any dependency groups. First we randomly choose a fraction (1 − p) of nodes in every layer as failed nodes. dF and dR are the failure threshold and the recovery threshold, respectively. Then if the ratio of failed nodes in every dependency group is larger than dF, the nodes in the dependency group are all failed because of cascading effect. If the ratio of failed nodes in a dependency group is below the dR, the failed nodes in the dependency group recover. The cascading effect in the dependency groups can be represented as below
Here, pg is the fraction of functional nodes in the dependency group. After dependency effect is caused by failed nodes, there is a percolation process in the layer. The largest connected component in a single layer can be obtained. In this study, we define two different effects between layers.

Effect 1 If a node in one layer does not belong to the largest connected component, other connected nodes will be invalid because of cascading effect between layers.

Here Fi is the set of failed nodes in the layer i, Cj is the largest connected component of layer j, and are dependent nodes in layer i and j, respectively, and w is the node index.

Effect 2 As long as there are nodes belonging to the largest connected component, other connected nodes in other layers can recover from failure because of cascading effect between layers.

The symbols in Eq. (4) are the same as Eq. (3). So in our model, after the initial removal, the multilayer network first experiences the dependency group effect. Then the percolation process within the layer begins, followed by the cascading effect between layers. At last, previous dependency groups will evolve into new dependency groups. The new dependency group also consists of randomly chosen nodes. The multilayer network will experience the dependency group effect and the cascading effect occurs iteratively until reaching a steady state. Note that there is no further failed nodes.

To illustrate our model mentioned above explicitly, we give an example of dependency process and percolation process in the single layer. In Fig. 1, the network is composed of 10 nodes, 12 links, and two dependency groups (dashed lines). Here dR = 0.4, dF = 0.6. In each group, if the fraction of failed nodes is equal to or larger than the failed threshold, the group will fail. If the fraction of failed nodes is equal to or less than the recovery threshold, the group will recover. In Fig. 1, the gray nodes represent the initial random removal. The nodes removed due to the percolation process are marked in blue. The nodes recovered due to the dependency process are marked in green. The nodes removed due to the dependency process are marked in red. Initially, in Fig. 1(a) we choose two nodes in gray as initially removed nodes. The blue nodes in Fig. 1(a) are nodes removed due to percolation process. In Fig. 1(b), the nodes in dotted lines combine dependency groups. Because dR = 0.4, the dependency group on the right will recover, and the dependency group on the left will be failed. In Fig. 1(c), the dependency groups change. The dependency group on the top recovers and the dependency group at the bottom loses efficiency. In Fig. 1(d), the dependency groups change again. At this time, all the nodes in the network are failed, and the process of cascading failure ends.

Fig. 1. (color online) Dynamic dependency group in the single layer network.
3. Analysis on the cascading model
3.1. The theoretical solutions of the cascading model

In our model, every iteration can be seen as an independent process. Therefore, we just analyze one iteration, i.e., the first iteration. To analyze the cascading failure model, we focus on the dependency process, the percolation process, and the cascading process between layers. We can get the theoretical solutions of our model using the mean-field approximation and the generating function techniques. In the dependency process, we can derive the probabilities of a dependency group functioning and failing as

PR is the probability that a dependency group is functioning, and PF is the probability that a dependency group is failed. So when the ratio of dependency nodes is q, we can get the probability of a node functioning
In the percolation process, we can use the generating function to deduce the fraction of the largest connected component. The generating function[29] of degree distribution is G0(ε) = ΣkP(k)εk. Then the fraction of nodes that belong to the largest connected component is
Here u is the probability following an edge from a node to the largest connected component. According to the previous research, u satisfies the relation
where , and u ∈ [0,1].

In the cascading process between layers, the giant mutually connected component (GMCC)[30] is defined as

Sα is the largest connected component in layer α, and are dependent nodes between layers. So we can get the GMCC after the cascading process between layers.

With Effect 1, the GMCC is

With Effect 2, the GMCC is

3.2. The cascading model in the two-layer network

In this section, we focus on the two-layer Barabsi Albert (BA) network. BA network[31] is the scale free network whose distribution of the degree satisfies power law distribution

where C is a constant, λ = 3, and k is the node degree. When p, q, g, dR, and dF are determined, PR and PF can be calculated according to Eq. (5), then gD(p) can be obtained easily using Eq. (6). We use p1 as the fraction of removed nodes in layer 1 and p2 as that in layer 2. So we have

We can get the value of u according to

Using Eq. (10), the GMCC with Effect 1 is

We can also get the GMCC with Effect 2 with Eq. (11)

Following the same method, we can also get the GMCC in the two-layer Erdos Rnyi (ER) network,[32,33] which is a typical random network. The only difference is that the degree distribution of ER network is

where λ is the mean degree of the network.

To verify our theoretical solution, we compare the GMCC after first iteration with our theoretical value. We do simulation in the two-layer BA network and the two-layer ER network, as shown in Fig. 2 and Fig. 3, respectively. Here we set dR = 0.2, dF = 0.6, g = 10, and q = 0.4. Changing the proportion of removed nodes, it turns out that our theoretical value is close to the simulation. It is obvious that the multilayer network with Effect 2 is more robust than the network with Effect 1. This is because of the recovery mechanism between layers.

Fig. 2. (color online) The comparison of theory and simulation in two-layer networks. (a) The verification of the GMCC in the two-layer BA network; (b) the verification of the GMCC in the two-layer ER network.
Fig. 3. (color online) The influence of q in BA and ER networks. (a) The change of S under Effect 1. (b) The change of the number of iterative failures under Effect 1. (c) The change of S under Effect 2. (d) The change of the number of iterative failures under Effect 2.
4. The simulation analysis
4.1. The influence factors of the network robustness

In this section, we concentrate on the influence factors of the multilayer network robustness. For convenience, two-layer networks are used in the simulation. It is obvious that higher dR and lower dF make networks more robust. However, in reality, the cost of networks is limited. We cannot get ideal dR and dF. Thus in the following simulations, we study the other influence factors with determined dR and dF.

Here we construct two double-layers networks consisting of BA networks and ER networks respectively. In each layer, the network has 2 × 104 nodes. We set dR = 0.2, dF = 0.6, and g = 10. Figure 3 shows the influence of the proportion of the dependency groups on the network robustness under Effect 1 and Effect 2. The largest connected component and the number of iterative failures are used to show the change of network robustness. To ensure the accuracy of the simulation, the points in the figures are the mean values of 50 experiments. As shown in Figs. 3(a) and 3(b), under Effect 1, higher proportion of the dependency groups q leads to higher network robustness. However, when q increases, the number of iterative failures decreases. It means that the network breaks down faster. Figures 3(c) and 3(d) show that when the proportion of the dependency groups decreases, the robustness of networks increases. Besides, the number of iterative failures also increases as q decreases. Then we can conclude that under Effect 1, larger q makes networks more robust, while under Effect 2, lower q makes networks more robust. We can discover that the performances of BA networks and ER networks are similar. In our model, the structure of networks has very little impact on the network robustness.

Next, we concentrate on the influence of the group size g, which changes from 5 to 30. The simulation is performed in the double-layer networks. Here we set q = 0.6, dR = 0.2, and dF = 0.6. Figure 4 shows the influence of the group size g in the double-layer networks with different effects. Changes of the phase change threshold mean that the network robustness alters. It is obvious that under Effect 1, increasing g can enhance the network robustness. However, increasing g will reduce the network robustness under Effect 2. In both cases, increasing g increases the number of iterative failures.

Fig. 4. (color online) The influence of g in BA and ER networks. (a) The change of S under Effect 1. (b) The change of the number of iterative failures under Effect 1. (c) The change of S under Effect 2. (d) The change of the number of iterative failures under Effect 2.

Then we study how the number of layers affects the network robustness. So we compare failure thresholds in different multilayer networks. Figure 5 shows the process of cascading failure in 2-layer, 3-layer, and 4-layer networks with Effect 1 and Effect 2. We observe that with Effect 1, increasing the number of layers decreases the failure threshold, which means that the network becomes more vulnerable. In contrast, the network with more layers is more robust with Effect 2.

Fig. 5. (color online) The cascading failure in multilayer networks. (a) The cascading failure with Effect 1 in multilayer networks. (b) The cascading failure with Effect 2 in multilayer networks.
4.2. The network connection tightness

In the last section, we change the model parameters to alter the robustness of multilayer networks. In this section, we tend to change the structure of networks to find a way to increase the network robustness. It is easy to figure out that increasing the connection tightness of networks can increase the network robustness. So we generate different networks with different mean degrees to construct multilayer networks. From figures in Section Subsection 4.1, we can find that the failure threshold exists in our model. The failure threshold means when the fraction of originally failed nodes is greater than the threshold, the network will lose efficiency. Table 1 shows the threshold value of different networks with Effect 1 and Effect 2. It is obvious that increasing the mean degree of networks can increase threshold values. However, when the mean degree reaches a certain value, the threshold value increases slowly. In reality, increasing the network connection tightness may consume resources. Thus in our model, setting the mean degree as 8 is enough to guarantee the network robustness.

Table 1.

The threshold values of networks.

.
5. Conclusion

In this study, we investigate the cascading failure with dynamic dependency groups in multilayer networks. Here we build a cascading failure model considering the recovery mechanism and the effect between layers. In dynamic dependency groups, two probabilities, dR and dF are defined. The value of dR and dF determines the recovery and failure threshold of the dependency group. In multilayer networks, we study two effects between layers. Effect 1 reduces the network robustness, and Effect 2 helps to increase the robustness of network. The scale of the largest connected component is deduced after the first iteration of the cascading failure. Simulation results verify our theoretical solution. Under Effect 1, increasing q and g can enhance the network robustness. On the contrary, increasing q and g will decrease the network robustness under Effect 2. Furthermore, increasing the network connection tightness will enhance the network robustness. When the mean degree value of the network reaches a certain value, the network robustness increases slowly. Thus in our model, increasing the mean degree value to a certain value is enough to make the network robust.

Reference
[1] Costa L d F Rodrigues F A Cristino A S 2008 Genet. Mol. Biol. 31 591
[2] Sporns O 2011 Ann. N.Y. Acad. Sci. 1224 109
[3] Nardo A D Natale M D Giudicianni C Greco R Santonastaso G F 2017 Water Sci. Technol. Water Supply 18 767
[4] Wu B Liu P Xu X 2017 J. Cleaner Prod. 141 168
[5] Milanovic J V Zhu W 2017 IEEE Trans. Smart Grid 9 4637
[6] Wang Y Bi L Lina S Li M Shi H 2017 Physica 466 180
[7] Yang L X Yang X Liu J Zhu Q Gan C 2013 Appl. Math. Comput. 219 8705
[8] Liu H R Dong M R Yin R R Han L 2015 Chin. Phys. 24 050506
[9] Wang J W Rong L L 2011 Saf. Sci. 49 807
[10] Liu J Xiong Q Y Shi X Wang K Shi W R 2015 Chin. Phys. 24 076401
[11] Tian M Wang X Dong Z Zhu G Long J Dai D Zhang Q 2015 EPL 111 18007
[12] Li M Liu R R Jia C X Wang B H 2014 EPL 108 56002
[13] Mizutaka S Yakubo K 2015 Phys. Rev. 92 012814
[14] Lehmann J Bernasconi J 2010 Phys. Rev. 81 031129
[15] Witthaut D Timme M 2015 Phys. Rev. 92 032809
[16] Zhang Y Arenas A Osman Y 2018 Phys. Rev. E. 97 022307
[17] Mirzasoleiman B Babaei M Jalili M 2011 Phys. Rev. 84 046114
[18] Wang J Li Y Zheng Q 2015 Physica 430 242
[19] Wang J Jiang C Qian J 2014 Physica 393 535
[20] Parshani R Stanley H E 2011 Proc. Natl. Acad. Sci. U.S.A. 108 1007
[21] Wang H Li M Deng L Wang B H 2015 PLoS ONE 10 e0126674
[22] Kornbluth Y Lowinger S Cwilich G Buldyrev S V 2014 Phys. Rev. 89 032808
[23] Parshani R Buldyrev S V Havlin S 2010 Phys. Rev. Lett. 105 048701
[24] McCulloh I Carley K 2008 Social Network Change Detection Technical Report Carnegie Mellon University
[25] Bai Y N Huang N Wang L Wu Z X 2016 Sci. Rep. 6 37749
[26] Gong M Ma L Cai Q Jiao L 2015 Sci. Rep. 5 8439
[27] Hu F Yeung C H Yang S Wang W Zeng A 2016 Sci. Rep. 6 24522
[28] Majdandzic A Podobnik B Buldyrev S V Kenett D Y Havlin S Stanley H E 2014 Nat. Phys. 10 34
[29] Cohen R Havlin S 2010 Complex Networks: Structure, Robustness and Function Cambridge Cambridge University Press
[30] Buldyrev S V Parshani R Paul G Stanley H E Havlin S 2009 Nature 464 1025
[31] Barabási A L Albert R 1999 Science 286 509
[32] Li Y Tang G Song L J Xun Z P Xia H Hao D P 2013 Acta Phys. Sin. 62 046401 in Chinese
[33] Albert R Barabási A L 2002 Rev. Mod. Phys. 74 47